package SwordFingerOffer;

import java.util.ArrayList;
import java.util.List;

public class Q62_CircleLastRemaining {
    //== 约瑟夫环
    //0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

    public int lastRemaining(int n, int m) {
//        //这是约瑟夫环的解法
//        //这就是一个环
//        List<Integer> list = new ArrayList<>();
//        for (int i = 0; i < n; i++) {
//            list.add(i);
//        }
//        while (list.size() != 1){
//            list.remove(list.size() < m ? m % list.size() : m - 1);
//        }
//        return list.get(0);


        //此题额外要求删掉后从下一个位置开始计数
        //这就是一个环
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int index = 0;
        //加深求余运算的理解
        while (list.size() != 1){
            index = (index + m - 1) % list.size() ;
            list.remove(index);
        }

        return list.get(0);


    }

    public static void main(String[] args) {

//        Q62_CircleLastRemaining fun = new Q62_CircleLastRemaining();
//        System.out.println(fun.lastRemaining(5, 3));
        System.out.println(2%3);
    }
}
